home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-13 / trs141f.zip / NFMT.ZIP / NFMT.C < prev    next >
C/C++ Source or Header  |  1992-07-20  |  16KB  |  681 lines
  1. #include <stdio.h>
  2. #include <ctype.h>
  3. #include "config.h"
  4. #include "options.h"
  5.  
  6. /*
  7.  * NAME
  8.  *    nfmt - simple text formatter
  9.  *
  10.  * SYNOPSIS
  11.  *    usage: nfmt [ -cs ] [ -width ] [ -p prefix ] [ file ... ]
  12.  *
  13.  * DESCRIPTION
  14.  *    Nfmt is a simple text formatter, similar to the BSD program fmt(1),
  15.  *    but uses best-fit line breaking, by a simple version of
  16.  *
  17.  *        "Breaking Paragraphs into Lines",
  18.  *        Donald E. Knuth and Michael F. Plass,
  19.  *        "Software--Practice and Experience" 11 (1981) 1119-1184.
  20.  *
  21.  *    Tabs are expanded on input and re-introduced on output.
  22.  *
  23.  * OPTIONS
  24.  *    -c    Crown margin mode.  The indentation of the first line
  25.  *        of a paragraph must be different from the indentation
  26.  *        of the second.  Subsequent lines must have the same
  27.  *        indentation as the second line.
  28.  *
  29.  *    -s    Split lines only.
  30.  *
  31.  *    -width    Maximum line width (default 75).  Fmt prefers to make
  32.  *        lines about 7% shorter, to give it room to balance line
  33.  *        lengths.
  34.  *
  35.  *    -p prefix
  36.  *        Only lines beginning with the prefix (possibly preceded
  37.  *        by white space) are re-arranged; the prefix (with any
  38.  *        preceding white space) is stripped for the formatting and
  39.  *        re-attached to each formatted output line.  For example,
  40.  *
  41.  *            nfmt -p ' * '
  42.  *
  43.  *        formats C comments laid out in the normal way, leaving
  44.  *        the code unchanged.  The -p option may also be combined
  45.  *        with the other options.
  46.  *
  47.  * AUTHOR
  48.  *    Ross Paterson <rap@doc.ic.ac.uk>
  49.  *    Packaging and portability by Yossi Gil <yogi@cs.ubc.ca>
  50.  */
  51.  
  52. /*
  53.  * The following parameters represent the program's idea of what is "best".
  54.  * Adjust to taste, subject to the caveats given.
  55.  */
  56.  
  57. #define    WIDTH    75    /* longest permitted line length */
  58. #define    LEEWAY    15    /* 1/LEEWAY of line is best left unused */
  59.  
  60. /*
  61.  * Costs and bonuses are expressed as the equivalent departure from
  62.  * the optimal line length, multiplied by 10.
  63.  * e.g. assigning something a cost of 50 means that it is as bad as
  64.  * a line 5 characters too short or long.
  65.  * The definition of SHORT_COST(n) should not be changed.
  66.  * However, EQUIV(n) may need tuning.
  67.  */
  68.  
  69. typedef    long    COST;
  70. #define    MAXCOST    (~(((COST)1)<<(8*sizeof(COST)-1)))
  71.  
  72. #define    SQR(n)        ((n)*(n))
  73. #define    EQUIV(n)    SQR((COST)(n))
  74.  
  75. /* cost of a filled line longer or shorter than best_width */
  76. #define    SHORT_COST(n)    EQUIV((n)*10)
  77.  
  78. /* cost of the difference between adjacent filled lines */
  79. #define    RAGGED_COST(n)    (SHORT_COST(n)/2)
  80.  
  81. /* basic cost per line */
  82. #define    LINE_COST    EQUIV(70)
  83.  
  84. /* line break after the first word of a sentence */
  85. #define    WIDOW_COST    EQUIV(200)
  86.  
  87. /* line break before the last word of a sentence */
  88. #define    ORPHAN_COST    EQUIV(150)
  89.  
  90. /* line break at the end of a sentence */
  91. #define    SENTENCE_BONUS    EQUIV(50)
  92.  
  93. /* line break after close parenthesis */
  94. #define    PAREN_BONUS    EQUIV(40)
  95.  
  96. /* line break after other punctuation */
  97. #define    PUNCT_BONUS    EQUIV(40)
  98.  
  99. /* credit for breaking a long paragraph 1 line later */
  100. #define    LINE_CREDIT    EQUIV(30)
  101.  
  102. /*
  103.  * Size of paragraph buffer, in words and characters.
  104.  * Longer paragraphs are handled (cf. flush_paragraph()).
  105.  */
  106.  
  107. #define    MAXWORDS    1000
  108. #define    MAXCHARS    5000
  109.  
  110. /*
  111.  *    Extra ctype(3)-style macros
  112.  */
  113. #define    isopen(c)    (strchr("([`'\"", c) != NULL)
  114. #define    isclose(c)    (strchr(")]'\"", c) != NULL)
  115. #define    isperiod(c)    (strchr(".?!", c) != NULL)
  116.  
  117. /*
  118.  * Miscellaneous definitions
  119.  */
  120.  
  121. #define    reg    register
  122.  
  123. typedef    int    bool;
  124. #define    TRUE    1
  125. #define    FALSE    0
  126.  
  127. #define    until(c)    if (c) break
  128.  
  129. /*
  130.  *    Word descriptor structure
  131.  */
  132.  
  133. #define    WORD    struct _WORD
  134.  
  135. WORD {
  136.     /* static attributes determined during input */
  137.     char    *text;
  138.     short    length;        /* length of this word */
  139.     short    space;        /* the size of the following space */
  140.     bool    paren:1;    /* starts with open paren */
  141.     bool    period:1;    /* ends in [.?!])* */
  142.     bool    punct:1;    /* ends in punctuation */
  143.     /* the remaining fields are computed during the optimization */
  144.     short    line_length;    /* length of the best line starting here */
  145.     COST    best_cost;
  146.     WORD    *next_break;    /* break which achieves best_cost */
  147. };
  148.  
  149. /*
  150.  *    Forward declarations
  151.  */
  152.  
  153. extern    void    trim_prefix        ARGS((void));
  154. extern    void    fmt            ARGS((void));
  155. extern    bool    get_paragraph        ARGS((void));
  156. extern    int    get_line        ARGS((int c));
  157. extern    int    get_prefix         ARGS((void));
  158. extern    int    get_space        ARGS((int c));
  159. extern    int    copy_rest        ARGS((int c));
  160. extern    bool    same_para        ARGS((int c));
  161. extern    void    flush_paragraph        ARGS((void));
  162. extern    void    fmt_paragraph        ARGS((void));
  163. extern    void    check_punctuation    ARGS((WORD *w, char *finish));
  164. extern    COST    base_cost        ARGS((WORD *this));
  165. extern    COST    line_cost        ARGS((WORD *next, int len));
  166. extern    void    put_paragraph        ARGS((WORD *finish));
  167. extern    void    put_line        ARGS((WORD *w));
  168. extern    void    put_prefix        ARGS((int c));
  169. extern    void    put_space        ARGS((int space));
  170.  
  171. FILE    *infile;
  172.  
  173. /*
  174.  *    Option values and derived quantities
  175.  */
  176.  
  177. bool    crown = FALSE;
  178. bool    split = FALSE;        /* each line is a paragraph on its own */
  179. char    default_prefix[] = "";
  180. char    *prefix = default_prefix;
  181. int    prefix_length;
  182. int    prefix_lead_space;
  183. int    prefix_full_length;
  184. int    max_width = WIDTH;
  185. int    best_width;
  186.  
  187. main(argc, argv)
  188. reg    int    argc;
  189. reg    char    *argv[];
  190. {
  191. reg    int    i;
  192.  
  193.     OPTIONS    ("-cs -width -p prefix [ file ... ]")
  194.         FLAG    ('c', crown)
  195.         FLAG    ('s', split)
  196.         NUM_OPT    (max_width)
  197.         STRING    ('p', prefix)
  198.     ENDOPTS
  199.     best_width = max_width*(LEEWAY-1)/LEEWAY;
  200.     trim_prefix();
  201.  
  202.     if (argc == 1) {
  203.         infile = stdin;
  204.         fmt();
  205.     }
  206.     else
  207.         for (i = 1; i < argc; i++)
  208.             if ((infile = fopen(argv[i], "r")) == NULL)
  209.                 fprintf(stderr, "%s: can't read file '%s'\n",
  210.                     argv[0], argv[i]);
  211.             else {
  212.                 fmt();
  213.                 fclose(infile);
  214.             }
  215.     return 0;
  216. }
  217.  
  218. void
  219. trim_prefix()
  220. {
  221. reg    char    *s;
  222.  
  223.     prefix_lead_space = 0;
  224.     while (*prefix == ' ') {
  225.         prefix_lead_space++;
  226.         prefix++;
  227.     }
  228.     prefix_full_length = strlen(prefix);
  229.     s = prefix + prefix_full_length;
  230.     while (s > prefix && s[-1] == ' ')
  231.         s--;
  232.     *s = '\0';
  233.     prefix_length = s - prefix;
  234. }
  235.  
  236. int    in_column = 0;
  237. int    out_column = 0;
  238.  
  239. char    parabuf[MAXCHARS];    /* space for the paragraph text */
  240. WORD    word[MAXWORDS];
  241. WORD    *word_limit;
  242. char    *wptr;
  243.  
  244. int    first_indent;    /* indentation of first line */
  245. int    indent;        /* indentation of rest of current paragraph */
  246. int    prefix_indent;
  247. int    next_prefix_indent;
  248. bool    tabs = FALSE;    /* tabs in input? */
  249.  
  250. int    next_char;    /* one-character look-ahead */
  251. char    *to_match = "";
  252.  
  253. void
  254. fmt()
  255. {
  256.     next_char = get_prefix();
  257.     while (get_paragraph()) {
  258.         fmt_paragraph();
  259.         put_paragraph(word_limit);
  260.     }
  261. }
  262.  
  263. /*
  264.  * Definitions.
  265.  *
  266.  * A <paragraph> is a maximal non-empty set of consecutive non-blank
  267.  * lines at the same indent.
  268.  * In split mode, a paragraph is a single non-blank line.
  269.  * In crown mode, the second and subsequent lines must have the same
  270.  * indentation, but differing from the first line.
  271.  * If a prefix is in effect, it must also be at the same indent for
  272.  * each line in the paragraph.
  273.  *
  274.  * A <word> is a maximal non-empty set of non-white characters.
  275.  *
  276.  * A <sentence break> is either the end of a paragraph or a word ending
  277.  * in [.?!], possibly followed by ) or ], followed by a word beginning
  278.  * with a capital.
  279.  */
  280.  
  281. bool
  282. get_paragraph()
  283. {
  284. reg    int    c;
  285.  
  286.     c = next_char;
  287.     /*
  288.      * Scan (and copy) blank lines,
  289.      * and lines not introduced by the prefix.
  290.      */
  291.     while (c == '\n' || *to_match ||
  292.            next_prefix_indent < prefix_lead_space ||
  293.            in_column < next_prefix_indent + prefix_full_length) {
  294.         if (prefix_length != 0)
  295.             c = copy_rest(c);
  296.     until(c == EOF);
  297.         putchar('\n');
  298.         c = get_prefix();
  299.     }
  300.     if (c == EOF) {
  301.         next_char = EOF;
  302.         return FALSE;
  303.     }
  304.     prefix_indent = next_prefix_indent;
  305.     wptr = parabuf;
  306.     word_limit = word;
  307.     if (split) {
  308.         first_indent = indent = in_column;
  309.         c = get_line(c);
  310.     }
  311.     else if (crown) {
  312.         first_indent = in_column;
  313.         c = get_line(c);
  314.         if (same_para(c) && in_column != first_indent) {
  315.             indent = in_column;
  316.             do {    /* for each line till the end of the para */
  317.                 c = get_line(c);
  318.             } while (same_para(c) && in_column == indent);
  319.         }
  320.         /*
  321.          * If only one line, use the secondary indent
  322.          * from last time (initially 0) if it splits.
  323.          */
  324.     }
  325.     else {
  326.         first_indent = indent = in_column;
  327.         do {    /* for each line till the end of the para */
  328.             c = get_line(c);
  329.         } while (same_para(c) && in_column == indent);
  330.     }
  331.     (word_limit-1)->period = TRUE;
  332.     next_char = c;
  333.     return TRUE;
  334. }
  335.  
  336. /*
  337.  * Copy a line which failed to match the prefix to the output,
  338.  * or which was blank after the prefix.
  339.  *
  340.  * In the former case, c is the character that failed to match *to_match.
  341.  * In the latter, c is \n or EOF.
  342.  * Returns the character ending the line.
  343.  */
  344. int
  345. copy_rest(c)
  346. reg    int    c;
  347. {
  348. reg    char    *s;
  349.  
  350.     out_column = 0;
  351.     put_space(next_prefix_indent);
  352.     for (s = prefix; s != to_match; s++)
  353.         putchar(*s);
  354.     if (c != '\n' && c != EOF) {
  355.         out_column += to_match - prefix;
  356.         put_space(in_column - out_column);
  357.         do {
  358.             putchar(c);
  359.             c = getc(infile);
  360.         } while (c != '\n' && c != EOF);
  361.     }
  362.     return c;
  363. }
  364.  
  365. bool
  366. same_para(c)
  367. reg    int    c;
  368. {
  369.     return next_prefix_indent == prefix_indent && *to_match == '\0' &&
  370.            c != '\n' && c != EOF;
  371. }
  372.  
  373. /*
  374.  * Read a line, given first non-blank character c, and the following
  375.  * indent, returning the first non-blank character of the next line.
  376.  */
  377. int
  378. get_line(c)
  379. reg    int    c;
  380. {
  381.     int    start;
  382. reg    char    *end_of_parabuf;
  383. reg    WORD    *end_of_word;
  384.  
  385.     end_of_parabuf = ¶buf[MAXCHARS];
  386.     end_of_word = &word[MAXWORDS-2];
  387.  
  388.     do {    /* for each word in a line */
  389.         /* scan word */
  390.         if (islower(c) && word_limit != word)
  391.             (word_limit-1)->period = FALSE;
  392.         word_limit->text = wptr;
  393.         do {
  394.             if (wptr == end_of_parabuf)
  395.                 flush_paragraph();
  396.             *wptr++ = c;
  397.             c = getc(infile);
  398.         } while (c != EOF && ! isspace(c));
  399.         check_punctuation(word_limit, wptr-1);
  400.         in_column += word_limit->length = wptr - word_limit->text;
  401.         if (wptr == end_of_parabuf || word_limit == end_of_word)
  402.             flush_paragraph();
  403.         *wptr++ = '\0';
  404.         /* scan inter-word space */
  405.         start = in_column;
  406.         c = get_space(c);
  407.         word_limit->space = in_column - start;
  408.         word_limit++;
  409.         if (c == EOF)
  410.             return EOF;
  411.     } while (c != '\n');
  412.     c = get_prefix();
  413.     (word_limit-1)->space =
  414.         c != EOF && ! islower(c) && (word_limit-1)->period ? 2 : 1;
  415.     return c;
  416. }
  417.  
  418. int
  419. get_prefix()
  420. {
  421. reg    int    c;
  422.  
  423.     in_column = 0;
  424.     c = get_space(getc(infile));
  425.     to_match = prefix;
  426.     if (prefix_length == 0)
  427.         next_prefix_indent = 0;
  428.     else {
  429.         next_prefix_indent = in_column;
  430.         while (*to_match && c == *to_match) {
  431.             in_column++;
  432.             to_match++;
  433.             c = getc(infile);
  434.         }
  435.         if (*to_match == '\0')
  436.             c = get_space(c);
  437.     }
  438.     return c;
  439. }
  440.  
  441. /*
  442.  * Scan blank characters, keeping in_column up-to-date.
  443.  */
  444. int
  445. get_space(c)
  446. reg    int    c;
  447. {
  448.     for (;;) {
  449.         if (c == ' ')
  450.             in_column++;
  451.         else if (c == '\t') {
  452.             tabs = TRUE;
  453.             in_column = (in_column/8 + 1)*8;
  454.         }
  455.         else
  456.             return c;
  457.         c = getc(infile);
  458.     }
  459. }
  460.  
  461. void
  462. check_punctuation(w, finish)
  463. reg    WORD    *w;
  464. reg    char    *finish;
  465. {
  466. reg    char    *start;
  467.  
  468.     start = w->text;
  469.     w->paren = isopen(*start);
  470.     w->punct = ispunct(*finish);
  471.     while (isclose(*finish) && finish > start)
  472.         finish--;
  473.     w->period = isperiod(*finish);
  474. }
  475.  
  476. /*
  477.  *    On hitting the limit, flush part of the paragraph to make room.
  478.  */
  479. void
  480. flush_paragraph()
  481. {
  482.     WORD    saved_last_word;
  483.     WORD    *split_point;
  484. reg    WORD    *w;
  485.     int    shift;
  486.     COST    best_break;
  487.  
  488.     /*
  489.      * In the special case where it's all one word, we just flush it.
  490.      */
  491.     if (word_limit == word) {
  492.         printf("%*s", wptr-parabuf, parabuf);
  493.         wptr = parabuf;
  494.         return;
  495.     }
  496.     /*
  497.      * Otherwise:
  498.      *    - format what you have so far as a paragraph,
  499.      *    - find a low-cost line break near the end,
  500.      *    - output to there,
  501.      *    - make that the start of the paragraph.
  502.      */
  503.     saved_last_word = *word_limit;
  504.     fmt_paragraph();
  505.     /* choose a good split point */
  506.     split_point = word;
  507.     best_break = MAXCOST;
  508.     for (w = word->next_break; w != word_limit; w = w->next_break) {
  509.         if (w->best_cost - w->next_break->best_cost < best_break) {
  510.             split_point = w;
  511.             best_break = w->best_cost - w->next_break->best_cost;
  512.         }
  513.         if (best_break <= MAXCOST - LINE_CREDIT)
  514.             best_break += LINE_CREDIT;
  515.     }
  516.     if (split_point == word) {
  517.         fprintf(stderr, "%s: panic\n", O_name);
  518.         exit(1);
  519.     }
  520.     put_paragraph(split_point);
  521.     *word_limit = saved_last_word;
  522.     /* copy text of words down to start of parabuf */
  523.     memcpy(parabuf, split_point->text, wptr - split_point->text);
  524.     shift = split_point->text - parabuf;
  525.     wptr -= shift;
  526.     /* adjust text pointers */
  527.     for (w = split_point; w <= word_limit; w++)
  528.         w->text -= shift;
  529.     /* copy words from split_point down to word */
  530.     memcpy((char *)word, (char *)split_point,
  531.         (word_limit - split_point + 1)*sizeof(WORD));
  532.     word_limit -= split_point - word;
  533. }
  534.  
  535. /*
  536.  * Compute the optimal formatting for the whole paragraph by computing and
  537.  * remembering the optimal formatting for each suffix from the empty one
  538.  * to the whole paragraph.
  539.  */
  540. void
  541. fmt_paragraph()
  542. {
  543. reg    WORD    *start, *w;
  544. reg    int    len;
  545. reg    COST    wcost, best;
  546.  
  547.     word_limit->best_cost = 0;
  548.     word_limit->length = max_width;        /* sentinel */
  549.  
  550.     for (start = word_limit-1; start >= word; start--) {
  551.         best = MAXCOST;
  552.         len = start == word ? first_indent : indent;
  553.         /* at least one word, however long, in the line */
  554.         w = start;
  555.         len += w->length;
  556.         do {
  557.             w++;
  558.             /* consider breaking before w */
  559.             wcost = line_cost(w, len) + w->best_cost;
  560.             if (wcost < best) {
  561.                 best = wcost;
  562.                 start->next_break = w;
  563.                 start->line_length = len;
  564.             }
  565.             len += (w-1)->space;    /* w > start >= word */
  566.             len += w->length;
  567.         } while (len < max_width);
  568.         start->best_cost = best + base_cost(start);
  569.     }
  570. }
  571.  
  572. /* constant component of cost of breaking before this word */
  573. COST
  574. base_cost(this)
  575. reg    WORD    *this;
  576. {
  577. reg    COST    cost;
  578.  
  579.     cost = LINE_COST;
  580.  
  581.     if (this > word)
  582.         if ((this-1)->period)
  583.             cost -= SENTENCE_BONUS;
  584.         else if ((this-1)->punct)
  585.             cost -= PUNCT_BONUS;
  586.         else if (this > word+1 && (this-2)->period)
  587.             cost += WIDOW_COST/((this-1)->length+2);
  588.  
  589.     if (this->paren)
  590.         cost -= PAREN_BONUS;
  591.     else if (this->period)
  592.         cost += ORPHAN_COST/(this->length+2);
  593.  
  594.     return cost;
  595. }
  596.  
  597. /* length-dependent component of cost of breaking at next */
  598. COST
  599. line_cost(next, len)
  600. reg    WORD    *next;
  601. reg    int    len;
  602. {
  603. reg    int    n;
  604. reg    COST    cost;
  605.  
  606.     if (next == word_limit)
  607.         return 0;
  608.     n = best_width - len;
  609.     cost = SHORT_COST(n);
  610.     if (next->next_break != word_limit) {
  611.         n = len - next->line_length;
  612.         cost += RAGGED_COST(n);
  613.     }
  614.     return cost;
  615. }
  616.  
  617. void
  618. put_paragraph(finish)
  619. reg    WORD    *finish; /* must be in the next_break chain from word */
  620. {
  621. reg    WORD    *w;
  622.  
  623.     out_column = 0;
  624.     put_prefix(first_indent);
  625.     put_line(word);
  626.     for (w = word->next_break; w != finish; w = w->next_break) {
  627.         put_prefix(indent);
  628.         put_line(w);
  629.     }
  630. }
  631.  
  632. void
  633. put_line(w)
  634. reg    WORD    *w;
  635. {
  636. reg    WORD    *endline;
  637.  
  638.     endline = w->next_break-1;
  639.     out_column += w->length;
  640.     fputs(w->text, stdout);
  641.     while (w != endline) {
  642.         put_space(w->space);
  643.         w++;
  644.         fputs(w->text, stdout);
  645.         out_column += w->length;
  646.     }
  647.     putchar('\n');
  648. }
  649.  
  650. void
  651. put_prefix(space)
  652.     int    space;
  653. {
  654.     out_column = 0;
  655.     put_space(prefix_indent);
  656.     fputs(prefix, stdout);
  657.     out_column += prefix_length;
  658.     put_space(space - out_column);
  659. }
  660.  
  661. void
  662. put_space(space)
  663.     int    space;
  664. {
  665. reg    int    space_target, tab_target;
  666.  
  667.     space_target = out_column + space;
  668.     if (tabs) {
  669.         tab_target = space_target/8*8;
  670.         if (out_column+1 < tab_target)
  671.             while (out_column < tab_target) {
  672.                 putchar('\t');
  673.                 out_column = (out_column/8 + 1)*8;
  674.             }
  675.     }
  676.     while (out_column < space_target) {
  677.         putchar(' ');
  678.         out_column++;
  679.     }
  680. }
  681.